COMMENT ⊗   VALID 00009 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.SS(Problems)
C00004 00003	.SS(Problems)
C00005 00004	.SS(Problems)
C00006 00005	.SS(Problems involving list-notation)
C00008 00006	.SS(Problems)
C00010 00007	.SS(Problems)
C00013 00008	.SS(Problems involving %3prog.)
C00015 00009	.SS(Hacking with %3eval%* and friends.)
C00016 ENDMK
C⊗;
.SS(Problems)
.BEGIN TABIT1(10);
I Which of the following are dotted-pairs.
\%21.%3 (X . Y)   %22.%3 ((A .(B . C))  %23.%3  A2   %24.%3 (X . Y2 . Z)
.GROUP SKIP 2;
%1
II Write the following as binary trees.
\%21.%3  ((A . B).(B . (C . D)))  %22.%3  (A . B).C).E)
\%23.%3  ((X . NIL).(Y .(Z . NIL)))    %24.%3  (NIL . NIL)
.GROUP SKIP 2;
%1
.GROUP
III Write the following binary trees as Sexprs.

\%21.              2.                       3.        
\%3                    A  
\  A 
\     B  C                                  A 

\			  B

\			                          B

\		 C   NIL       D    E  

\						     C  NIL



.APART
.GROUP
%2
\4.                                5.
%3
\    CAR            NIL 

\	                            CONS        X         Y  NIL


\		    QUOTE         A    NIL

.APART
.END

.SS(Problems)
%1
.BEGIN TABIT1(40);CENTERIT;
.GROUP
I Evaluate the following

←%21.%3 eq[X;Y]   %22.%3 cons[X;Y]   %23.%3 car[(X . Y)]   %24.%3 car[cons[X;Y]]

%25.%3 cadr[(X .(Y . NIL))]   \%26.%3 cdar[(X .(Y . NIL))]
.APART

%27.%3 eq[cdr[(A . B)];cdr[(C . B)]]   \%28.%3 atom[cons[(A . B);(C . D)]]

%29.%3 cons[atom[A];atom[(A . B)]]   \%210.%3 eq[atom[ATOM];atom[EQ]]

←%211.%3 [T → A; T → B]   %212.%3 [NIL → A; T → B]   %213.%3 [eq[A;B] → 4]

%214.%3 [atom[X] → atom[X]; T → FOO]   \%215.%3 [eq[EQ;X] → A; eq[A;B] → B; T → C]

←%216.%3 cons[[eq[A;B] → 1; T → FOO];cons[A;cadr[(A .(B .C))]]]
.END

.SS(Problems)
.BEGIN CENTERIT;TABIT2(10,23);SELECT 1;
I  Use the following definition:
.GROUP;

%3
\  twist[s] <=\[atom[s] → s;
\\ T → cons[twist[cdr[s]];twist[car[s]]]]
%1

and evaluate: 
%21.%3 twist[A]   %22.%3 twist[(A . B)]   %23.%3 twist[((A . B). C)]
.APART
.GROUP

%1
Now try:
%3
\findem[x;y] <=\[atom[x] → [eq[x;y] → T; T → NIL];
\\ T → cons[findem[car[x];y];findem[cdr[x];y]]]
%1

and evaluate:
%21.%3 findem[(A . B);A]   %22.%3 findem[(B .(A . C));A]
%23.%3 findem[(B .(A . C));C]   %24.%3 findem[(A . B);(A . B)]
.APART

.END
.SS(Problems involving list-notation)
.BEGIN CENTERIT;SELECT 1;
.GROUP
I  Translate the following lists into Sexpr dotted-pair notation.
←%21.%3 (A B C)   %22.%3 (A)   %23.%3 ((A))   %24.%3 (A (B (C))).

.APART
.GROUP
%1

Now go the other way and translate the following sexprs into list notation.
←%25.%3 ((A .(B . NIL)).((C . NIL). NIL))   %26.%3 (NIL . NIL)
←%27.%3 ((CONS .((QUOTE .(A . NIL)). NIL))
.APART
.GROUP
%1

VII  Evaluate the following, writing the results in list notation where possible.
←%21.%3 car[(A B)]   %22.%3 cdr[(A B)]   %23.%3 cons[A;(B C)]   %24.%3 cons[A;NIL]
←%25.%3 cons[eq[A;A];(A B C)]
.END
.SS(Problems)
.BEGIN CENTERIT;TABIT2(10,23);SELECT 1;
.GROUP
I  Use the following defintion:
%3
\match[k;m] <=\[null[k] → NO;
\\ null[m] → NO;
\\ eq[car[k];car[m]] → car[k];
\\ T → match[cdr[k];cdr[m]]]

%1
and evaluate:
%21.%3 match[(X);(X)]   %22.%3 match[(A B E);(J O E)]  %23.%3 match[(F O O); (BAZ)]
.APART
%1
.GROUP

IX  Now write your own.

%21.%3 among[x;y] <= ... : among%1 is to be a predicate; %3x%1 is an atom; %3y%1 is a list
of atoms.  %3among%1 is to return %3NIL%1 if %3x%1 is not found as an element of %3y%1; o.w.
among is to return %3T%1.

.NOFILL
\e.g. %3among[A;(A B C)] = among[A;(C D E A)] = T
\     among[A1;(A2 B2)] = NIL.
.FILL
%1

%22.%3 anywhere[x;y] <= ... : anywhere%1 is a predicate; %3x%1 is an atom; %3y%1 is an arbitrary
sexpr. %3anywhere%1 is to return %3T%1 just in the case that %3x%1 appears somewhere in %3y%1.
.NOFILL

\e.g. %3anywhere[A;(A B C)] = anywhere[A;((A . B). C)] = T
\     anywhere[A;(B C D)] = NIL.
.FILL
%1

.END
.SS(Problems)
.BEGIN CENTERIT;TABIT3(10,25,36);

.GROUP;
←%2I. The Great Mother of All Functions!!! (⊗→%3tgmoaf%*↔←)
%3

\tgmoaf[x] <= \[atom[x] →\[eq[x ;T] → T;
\\\ eq[x;NIL] → NIL;
\\\ T → TRYAGAINNEXTWEEK];
\\ eq[car[x];QUOTE] → cadr[x];
\\ eq[car[x];CAR] → car[tgmoaf[cadr[x]]];
\\ eq[car[x];CDR] → cdr[tgmoaf[cadr[x]]];
\\ eq[car[x];CONS] → cons[tgmoaf[cadr[x]];tgmoaf[caddr[x]]];
\\ eq[car[x];ATOM] → atom[tgmoaf[cadr[x]]];
\\ eq[car[x];EQ] → eq[tgmoaf[cadr[x]];tgmoaf[caddr[x]]];
\\ T → TRYAGAINNEXTWEEK]
%1
.APART
.GROUP

Evaluate the following:

%21.%3 tgmoaf[T]
%22.%3 tgmoaf[A]
%23.%3 tgmoaf[(CAR(QUOTE(A . B)))]
%24.%3 tgmoaf[(CDR (QUOTE (A B)))]
%25.%3 tgmoaf[(EQ (CAR (QUOTE (A . B)))(QUOTE A))]
%26.%3 tgmoaf[(EQ (CAR (QUOTE (A . B))) A)]
%27.%3 tgmoaf[(ATOM (CAR (QUOTE (A B))))]
.APART

.GROUP


←%2II. The Great Mother of All Functions Revisited!!!(⊗→%3tgmoafr%*↔←)
%3

\tgmoafr[x] <= \[atom[x] →\[eq[x;T] → T;
\\\ eq[x;NIL] → NIL;
\\\ T → TRYAGAINNEXTWEEK];
\\ eq[car[x];QUOTE] → cadr[x];
\\ eq[car[x];CAR] → car[tgmoafr[cadr[x]]];
\\ eq[car[x];CDR] → cdr[tgmoafr[cadr[x]]];
\\ eq[car[x];CONS] → cons[tgmoafr[cadr[x]];tgmoafr[caddr[x]]];
\\ eq[car[x];ATOM] → atom[tgmoafr[cadr[x]]];
\\ eq[car[x];COND] → evcond[cdr[x]];
\\ T → TRYAGAINNEXTWEEK]
.APART
.GROUP

\evcond[x] <=\[tgmoafr[caar[x]] → tgmoafr[cadar[x]];
\\ T → evcond[cdr[x]] ]
.APART
.GROUP
%1

Evaluate the following:

%21.%3 tgmoafr[T]
%22.%3 tgmoafr[(CDR (QUOTE (A B)))]
%23.%3 tgmoafr[(EQ (CAR (QUOTE (A . B))) (QUOTE A))]
%24.%3 tgmoafr[(COND((EQ (CAR (QUOTE (A . B)))(QUOTE A))(QUOTE FOO)))]
%25.%3 tgmoafr[(COND((ATOM (QUOTE (A)))(QUOTE FOO))(T(QUOTE BAZ)))]
.APART
.END


.SS(Problems involving %3prog.)
.BEGIN SELECT 1;TABIT1(10);CENTERIT;
.GROUP
Write %3prog%*-versions of the following functions (or predicates).

%21.%3 member[x;y]<= ... : x%1 is atomic; %3y%* is a list of atoms.  %3member%* is to 
return %3T%* just in the case that %3x%* is one of the elements in %3y%*.
.APART

%22.%1 The factorial funciion.

%23.%3  delete[x;y]<= ... : x%1 is atomic; %3y%* is a list of atoms.  %3delete%* is to 
return a list which looks like %3y%*, except all occurrences of %3x%*
have been deleted.

%24.%1 The %3append%* function.

%25.%3  last[x]<= ... : x%1 is a non-empty list.  %3last%* is to return the last 
element in %3x%*.

%26.%1  Now write the Sexpr translations of each of your functions.
.GROUP


.END
.SS(Hacking with %3eval%* and friends.)
.BEGIN SELECT 1;CENTERIT;

Assume that the variable, %3st%1, is currently bound to:
.NOFILL
←%3((X . M)(Y . T)(Z .(M N))(T . T)).
%1

evaluate:

%21.%3 assoc[Z;st]
.APART
%22.%3 eval[(QUOTE A);st]
%23.%3 apply[CONS;(A B); st]
%24.%3 apply[CAR;((A));st]
%25.%3 apply[CAR;(A);st]

.FILL
.END